package com.itheima.datastructure.stack;

import java.util.LinkedList;

public class E03InfixToSuffix {
    public static void main(String[] args) {
        System.out.println(infixToSuffix("a+b"));
        System.out.println(infixToSuffix("a+b-c"));
        System.out.println(infixToSuffix("a+b*c"));
        System.out.println(infixToSuffix("a*b-c"));
        System.out.println(infixToSuffix("(a+b)*c"));
        System.out.println(infixToSuffix("(a+b*c-d)*e"));
        System.out.println(infixToSuffix("a*(b+c)"));
    }
    /*
    符号优先级比栈顶元素高的入栈
    否则吧栈里优先级>=他的都出栈，它再入栈
    遍历完成，栈里剩余的运算符依次出栈
    左括号直接入栈，优先级为0，
    遇到右括号左括号出栈
     */
    static int priority(char c){
        return switch (c){
            case'*','/'->2;
            case '+','-'->1;
            case '('->0;
            default -> throw new IllegalArgumentException("不合法的运算符："+c);
        };
    }

    static String infixToSuffix(String exp){
        LinkedList<Character> stack=new LinkedList<>();
        StringBuilder sb=new StringBuilder(exp.length());
        for(int i=0;i<exp.length();i++){
            char c=exp.charAt(i);
            switch (c){
                case '*','/','+','-'->{
                    if(stack.isEmpty()){
                        stack.push(c);
                    }else{
                        if(priority(c)>priority(stack.peek())){
                            stack.push(c);
                        }else{
                            while(!stack.isEmpty() && priority(stack.peek())>=priority(c)){
                                sb.append(stack.pop());
                            }
                            stack.push(c);
                        }
                    }
                }
                case '('->{
                    stack.push(c);
                }
                case')'->{
                    while(!stack.isEmpty() && stack.peek()!='('){
                        sb.append(stack.pop());
                    }
                    stack.pop();
                }
                default -> {
                    sb.append(c);
                }
            }
        }
        while(!stack.isEmpty()){
            sb.append(stack.pop());
        }
        return sb.toString();
    }

}
